package offer.offer03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 99, 100 使用滑动窗, 注意对于数组全员全负数的情况单独找最小值, 因为这种情况比较少, 所以不必要单独处理
 * 就滑动窗口, ==0的时候就把前面的都抛弃, 因为如果带上这一截是会变大的,
 * 则证明从端点到其中任何一个点都是>0的。
 * 但是既然我们是从左侧开始的, 那么从右端点那一截可能是负的, 所以得从后往前再过一遍。
 *
 * 条件分析: 数组有正有负, 所以不可能返回非正数……骗人的, 可以全负数
 */
public class Solution42 {
    public int maxSubArray(int[] nums) {
        //if(nums == null || nums.length == 0) return 0;
        List<Integer> list = new ArrayList<>();
        int sum = 0;

        int maxSum = 0;
        for(int i = 0; i < nums.length; i ++){
            sum += nums[i];
            if(sum < 0){
                sum = 0;
            }
            if(sum > maxSum){
                maxSum = sum;
            }
        }
        //如果这里没有任何一个正数, 找到其中的最大值返回(这是个非正数)
        if(maxSum == 0){
            Arrays.sort(nums);
            maxSum = nums[nums.length - 1];
        }
        return maxSum;
    }

    /**
     * 太强了……
     *
     * 改变了nums数组, 将nums[i]变为以nums[i]结尾的子数组的和的最大值……看解析吧。。
     */
    public int maxSubArray2(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }


    public static void main(String[] args) {
        //int[] input = new int[]{1, 2, 3, 4, -15, 3, 4, 5, 6, -2, -1, 4, -2, 1};
        int[] input = new int[]{-1, -4, -153, -32, -1, -34, -54, -2};
        System.out.println(new Solution42().maxSubArray(input));
    }
}
